package j2024.j202412;

//import j2024.j202407.ListNode;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class j1215 {
    /**
     * 48. 旋转图像
     * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     *
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        for (int i = 0; i < m/2; i++) {
            for (int j = 0; j < (n+1)/2; j++) {
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[m-j-1][i];
                    matrix[m-j-1][i] = matrix[m-i-1][m-j-1];
                    matrix[m-i-1][m-j-1] = matrix[j][m-i-1];
                    matrix[j][m-i-1] = tmp;
            }
        }
    }

    /**
     * 240. 搜索二维矩阵 II
     * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
     *
     * 每行的元素从左到右升序排列。
     * 每列的元素从上到下升序排列。
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m =  matrix.length,n = matrix[0].length;
        int i = m-1,j = 0;
        while(i>=0 && j<n){
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]>target){
                i--;
            }else if(matrix[i][j]<target){
                j++;
            }
        }
        return false;
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        int m =  matrix.length,n = matrix[0].length;
        int i = 0,j = n-1;
        while(i<m && j>=0){
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]>target){
                j--;
            }else if(matrix[i][j]<target){
                i++;
            }
        }
        return false;
    }

    /**
     * 160. 相交链表
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     *
     * 图示两个链表在节点 c1 开始相交：
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA,pB = headB;
        int lenA = 0,lenB = 0;
        while(pA!=null){
            pA = pA.next;
            lenA++;
        }
        while(pB!=null){
            pB = pB.next;
            lenB++;
        }
        int len = lenA-lenB;
        ListNode ret = null;
        if(len<0){
            ret = getCommon(pB,pA,-len);
        }else {
            ret = getCommon(pA,pB,len);
        }
        return ret;
    }
    public ListNode getCommon(ListNode headA, ListNode headB,int len) {
        while(len!=0){
            headA = headA.next;
            len--;
        }
        while(headA!=null && headB!=null){
            if(headA==headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}
